The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Network devices, such as network switches, routers, edge devices and the like, often employ lookup tables that store various information associated with packets processed by the network devices, and a network device performs lookups in the lookup tables for making various processing decisions during processing of packets by the network device. For example, lookup operations may be performed for packet classification, forwarding decisions, quality of service classifications, policy control list applications, and other processing operations generally performed by network devices. In general, a lookup for a packet is performed according to a key associated with or generated for the packet. The key is used to search a table, for example, and information relevant to the packet (e.g., forwarding information for the packet) is retrieved from an entry in the table identified by the key.
Some lookup tables are implemented using content addressable memory (CAM). A CAM based table generally allows a key provided to the table to be compared against all of the entries of the table, typically in a single comparison cycle, and returns a result that is indicative of which entries match the key. However, CAM based tables generally are expensive in terms of area and power consumption, especially when large size lookup tables are employed.
An alternative implementation of a lookup table utilizes a hash based scheme in which a hash function is applied to a key to determine a location in the hash table at which the key and information associated with the key (e.g., forwarding information) are stored. While hash tables are generally smaller and more efficient compared to CAM implementations, hash tables exhibit inherent collisions when a hash function generates a same hash value for two or more different keys provided to the hash function, and as a result, some keys provided to a hash table cannot be inserted into the hash table. Therefore, a lookup operation for some keys provided to a hash table will not produce a match, even though a key may match an entry. Thus, it is difficult to achieve exact match lookup performance when hash tables are employed.